#include <iostream>
#include <vector>
using namespace std;

int ans;

void findKthLargest(vector<int>& nums, int l, int r, int k) {
    if (l > r) return;
    int rd = l + rand() % (r - l + 1);
    swap(nums[l], nums[rd]);
    int i = l, j = r;
    while (i < j) {
        while (i <= r && nums[i] <= nums[l]) ++i;
        while (j >= l && nums[j] > nums[l]) --j;
        if (i < j) swap(nums[i], nums[j]);
    }
    swap(nums[l], nums[j]);
    if (j == nums.size() - k) {
        ans = nums[j];
        return;
    } else if (j > nums.size() - k) {
        findKthLargest(nums, l, j - 1, k);
    } else {
        findKthLargest(nums, j + 1, r, k);
    }
}


int findKthLargest(vector<int>& nums, int k) {
    findKthLargest(nums, 0, nums.size() - 1, k);
    return ans;
}